package com.fengdi.book.hard;

import java.util.*;

/**
 * @Description 动态规划算法
 * @Date 10:16
 */
public class DynamicAssign {
    public static class MaxProduct {
        public int maxProduct(int[] nums) {
            // max[i] 表示以 i 为结尾子数组乘积的最大值， min[i] 表示以 i 为结尾子数组乘积的最小值
            int len = nums.length;
            if(len == 1) return nums[0];

            int[] max = new int[len];
            int[] min = new int[len];

            max[0] = nums[0];
            min[0] = nums[0];
            int res = max[0];

            for(int i = 1; i < len; i++) {
                max[i] = Math.max(nums[i], Math.max(nums[i] * max[i - 1], nums[i] * min[i - 1]));
                min[i] = Math.min(nums[i], Math.min(nums[i] * max[i - 1], nums[i] * min[i - 1]));
                res = Math.max(res, max[i]);
            }

            return res;
        }
    }

    public static class MaxProfit {
        public int maxProfit(int[] prices) {
            int len = prices.length;
            int[][] dp = new int[len][4];// 0 持有 1 当天未持有 2 当天卖了 3 昨天刚卖
            dp[0][0] = -prices[0];

            for(int i = 1; i < len; i++) {
                dp[i][0] = Math.max(dp[i-1][0], Math.max(
                   dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]
                ));

                dp[i][1] = Math.max(dp[i-1][0], Math.max(dp[i-1][1],dp[i-1][2]));
                dp[i][2] = dp[i-1][0] + prices[i];
                if(i==1) {
                    dp[i][3] = 0;
                }else {
                    dp[i][3] = dp[i-2][0] + prices[i-1];
                }
            }

            return Math.max(
                    dp[len-1][2], Math.max(dp[len-1][1], dp[len-1][3])
            );
        }
    }

    public static class NumSquares {
        public int numSquares(int n) {
            int[] dp = new int[n+1]; // dp[i]表示和为i的完全平方数的最小数量
            for(int i = 1; i <= n; i++) {
                int min = Integer.MAX_VALUE - 1;
                for(int j = 1; j * j <= i; j++) {
                    min = Math.min(min, dp[i - j*j]);
                }
                dp[i] = min + 1;
            }
            return dp[n];
        }
    }

    public static class WordBreak {
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<Integer> lens = new HashSet<>();
            int len = s.length();
            boolean[] dp = new boolean[len+1];

            for(String word : wordDict) {
                lens.add(word.length());
            }
            dp[0] = true;

            for(int i = 0; i <= len; i++) {
                if(dp[i]) {
                    for(Integer le : lens) {
                        if(le + i > len) {
                            continue;
                        }
                        String cap = s.substring(i, le + i);
                        if(wordDict.contains(cap)) {
                            dp[i+le] = true;
                        }
                    }
                }
            }

            return dp[len];
        }
    }

    public static class WordBreakV2 {
        public List<String> wordBreak(String s, List<String> wordDict) {
            // 用一个map来存放以每一个index开始的部分可以组成的句子列表
            Map<Integer, List<List<String>>> map = new HashMap<>();
            List<List<String>> wordBreaks = this.backtrace(s, s.length(), new HashSet<>(wordDict), 0, map);
            List<String> breakList = new ArrayList<>();
            // 组成句子
            for(List<String> wordBreak : wordBreaks) {
                breakList.add(String.join(" ", wordBreak));
            }
            return breakList;
        }

        private List<List<String>> backtrace(String s, int length, Set<String> wordDict, int index, Map<Integer, List<List<String>>> map) {
            if(!map.containsKey(index)) {
                List<List<String>> wordBreaks = new LinkedList<>();
                if(index == length) {
                    wordBreaks.add(new LinkedList<>());
                }

                for(int i = index + 1; i <= length; i++) {
                    String word = s.substring(index, i);
                    if (wordDict.contains(word)) {
                        List<List<String>> nextWordBreaks = this.backtrace(s, length, wordDict, i, map);
                        for(List<String> nextWordBreak : nextWordBreaks) {
                            LinkedList<String> wordBreak = new LinkedList<>(nextWordBreak);
                            wordBreak.offerFirst(word);
                            wordBreaks.add(wordBreak);
                        }
                    }
                }
                map.put(index, wordBreaks);
            }
            return map.get(index);
        }
    }

    public static class MaxCoins {
        public int maxCoins(int[] nums) {
            int len = nums.length;
            int nLen = len + 2;
            int[] newNums = new int[nLen];
            newNums[0] = newNums[newNums.length - 1] = 1;

            // 创建包含边界的数组
            System.arraycopy(nums, 0, newNums, 1, len);

            int[][] dp = new int[nLen][nLen];

            for(int x = 2; x < nLen; x++) {
                for(int i = 0; i < nLen - x; i++) {
                    this.getMaxCoins(i, i + x, dp, newNums);
                }
            }

            return dp[0][nLen - 1];
        }

        /**
         * @Description 获取区间内可以获取的最大硬币数量
         * @Date 2025/10/9
         * @param l 左边界
         * @param r 右边界
         * @param dp 动态规划辅助数组
         * @param ns 扩充数组
         */
        private void getMaxCoins(int l, int r, int[][] dp, int[] ns) {
            int max = 0;
            for(int i = l + 1; i < r; i++) {
                int leftCoins = dp[l][i];
                int rightCoins = dp[i][r];
                int t = leftCoins + rightCoins + ns[l] * ns[i] * ns[r];
                max = Math.max(max, t);
            }
            dp[l][r] = max;
        }
    }
}
